package tree;

import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//中序遍历
public class leetcode94 {
    public static void main(String[] args) {
        Integer[] nums = {1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9};
        TreeNode root = createTree(nums);
//        TreeNode.printTree(root);
        List<Integer> results = new ArrayList<>();
        results =  inorderTraversal(root, results);
        for (int i = 0; i < results.size(); i++) {
            System.out.print(results.get(i) + " ");
        }
    }

    public static List<Integer> inorderTraversal(TreeNode root, List<Integer> results){
        if(root == null) return null;

        inorderTraversal(root.left, results);
        results.add(root.val);
        inorderTraversal(root.right, results);
        return results;
    }

    public static TreeNode createTree(Integer[] nums){
        if(nums == null || nums.length == 0) return null;

        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while(!queue.isEmpty() && i < nums.length){
            TreeNode curr = queue.poll();

            if(i<nums.length && nums[i] != null){
                curr.left = new TreeNode(nums[i]);
                queue.offer(curr.left);
            }
            i++;
            if(i<nums.length && nums[i] != null){
                curr.right = new TreeNode(nums[i]);
                queue.offer(curr.right);
            }
            i++;
        }
        return root;
    }
}
